#!/usr/bin/env python
#Author:Lynn <Lynn.lin@avocent.com>
# 03.20.2008
# Description: resolve dependency

def dep_alg(start,graph,li,cyc=[]):
	if not graph[start]:
		pass
	else:
		for dep in graph[start]:
			if dep in cyc :
				print 'loop happen'
                                graph[start].remove(dep)
			else:
				dep_alg(dep,graph,li,cyc+[dep])
	if start not in li:
		li.append(start)

if __name__ == '__main__':
	graph = {'v1':['v2','v3','v4'],'v2':[],'v3':['v2','v5'],'v4':['v5'],'v5':[],'v6':['v4','v5']}
	start = 'v1';
	li = []
	cyc = [start]
	dep_alg(start,graph,li,cyc)
	print li

